package 链表;

/**
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 示例1：
 * 2→4→3
 * 5→6→4
 * result:7→0→8
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807
 */
/*思路：①模拟题
已知条件： 三个链表，其中一个是创建的结果链表  一个储存进位
        实现加法模拟 >10 保留个位  下一位+1，
            加法模拟实现： 二者都不为空 则相加 若 一条为空 则将不为空的值直接加入result(改进 为空 则使其为0)
                        进位时也需要判断
        是否需要增加一位
        最后反转结果链表

*/
    /*  时间复杂度：O(\max(m,n))O(max(m,n))，
    其中 mm 和 nn 分别为两个链表的长度。我们要遍历两个链表的全部位置，
    而处理每个位置只需要 O(1)O(1) 的时间。
    空间复杂度：O(1)O(1)。注意返回值不计入空间复杂度*/

public class training2 {

    public ListNode addTwoNumber(ListNode l1, ListNode l2) {
        //结果链表
        ListNode result = new ListNode(0);
        //保证原始值不变 第三个语句则是定位头节点 且保证初始值不变
        ListNode p = l1, q = l2, curr = result;
        //进位存储值
        int temp = 0;
        while (p != null || q != null) {
            int x = p == null ? 0 : p.val;
            int y = q == null ? 0 : q.val;

            int sum = x + x + temp;
            temp = sum / 10;
            //需要新建一个节点
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p.next != null) p = p.next;
            if (q.next != null) q = q.next;
        }
        if (temp > 0) curr = new ListNode(temp);
    /*    初始化的节点 dummy head 没有存储值，最后返回 dummy head 的 next 。
    这样的好处是不用单独对 head 进行判断改变值。也就是如果一开始的 head 就是代表个位数，
    那么开始初始化的时候并不知道它的值是多少，所以还需要在进入循环前单独对它进行值的更正，
    不能像现在一样只用一个循环简洁*/
        return result.next;
    }


}
